package com.lfg.leetcode.leetcode100;


import java.util.HashMap;
import java.util.Map;

public class No149maxPoints {

    public static void main(String[] args) {
        int ret = maxPoints(Point.deserialize("[[1,1],[2,2],[3,3]]"));
        System.out.println(ret);
    }

    public static int maxPoints(Point[] points) {
        if (null == points) {
            return 0;
        }
        if (points.length < 3) {
            return points.length;
        }

        int ret = 0;
        for (Point point1 : points) {
            Map<String, Integer> data = new HashMap<>(points.length);
            int zero = 0;
            int line = 0;
            for (Point point2 : points) {
                if (point1.x == point2.x) {
                    if (point1.y == point2.y) {
                        zero++;
                    } else {
                        line++;
                    }
                } else {
                    int y = point1.y - point2.y;
                    int x = point1.x - point2.x;
                    int num = gcd(y, x);
                    String key = y / num + "/" + x / num;
                    int value = data.getOrDefault(key, 0) + 1;
                    data.put(key, value);
                }
            }
            int max = line;
            for (Map.Entry<String, Integer> entry : data.entrySet()) {
                max = Math.max(max, entry.getValue());
            }
            ret = Math.max(ret, zero + max);
            ret = Math.max(ret, line + zero);
        }
        return ret;
    }

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}
